Java 排序之插入排序、希尔排序

Java Java

创建时间:2019-08-26 10:43

字数:1.4k 阅读:

一、插入排序
二、希尔排序

今天学习了一下 Java 数组的相关操作，包含排序和查找，现在先将排序记录巩固一下。
常用并且比较重要的几种排序：插入排序、希尔排序、快速排序、归并排序、冒泡排序、选择排序。

一、插入排序

1. 插入排序算法思想

1) 普遍思想
插入排序的算法是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2) 我的理解与分析
我最初看到上面的思想，就是一脸懵逼，读都读不懂，又去找了很多资料，才能理解那么一点点，所以这里用通俗一点的话来解释：

假设有一个数组：

int[] arr = { 22, 11, 10, 55, 44 };

第 0 个元素 22 看作已经排好序；
取出第 1 个元素 11，在已经排序的元素序列中（第一步的 22）从后向前扫描；
如果新元素 11 比已排序的元素 22 小，就把 22 往后挪，并将 11 插入到前面。这个时候数组应该如下：
```
int[] arr = { 11, 22, 10, 55, 44 }
```
接着在取出第 2 个元素 10，与第一个元素 22 相比，如果比第一个元素小，就插入到 22 之前。这个时候数组应该如下：
```
int[] arr = { 11, 10, 22, 55, 44 }
```
10 插入后继续与前面的元素相比，小则插入，大则不动。这个时候数组应该如下：
```
int[] arr = { 10, 11, 22, 55, 44 }
```
取出第 3 个元素继续比较……

插入排序的特点：越有序，操作的次数越少，效率越高。

2. 算法图解附视频

插入排序图解

视频点此查看。

3. 算法代码

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = { 11, 22, 10, 55, 44 };
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {  // 从第一个元素开始遍历
            for (int j = i; (j > 0) && (arr[j] < arr[j - 1]); j--) {    // 条件：是否比前一个元素小，j-- 是为了挪位后再次与前一个元素比较
                int temp = arr[j];      // 把移动的元素暂时存起来
                arr[j] = arr[j - 1];    // 把大的元素往后挪
                arr[j - 1] = temp;      // 把小的元素放到前面
            }
        }
    }
}

二、希尔排序

1. 算法简介

希尔排序 是插入排序的改进版本。为什么是插入排序的改进版本呢？上面说过的插入排序，它是取出一个元素然后从后向前比较，如果小于就放到前面来，并且它的特点是 越有序，效率越高。对于插入排序，序列数据少的话还行，要是序列数据特别多，并且是无序，那么插入排序的效率就会很慢，所以就出现了一个希尔排序，使序列更 接近有序，这样的话，相对于插入排序操作数据较大的时候要快一点，不过它最终属于插入排序类中。

2. 算法分析

希尔排序，先将要排序的一组数据按某个增量 d(n/2，n 为排序数的个数) 分成若干组（把相隔 d 的数据分为一组），并在各组内进行直接插入排序，然后再用一个较小的增量 (d/2) 对它进行分组，在每组中再进行插入排序，当增量减到 1 时，进行插入排序后，排序完成。

假设有一个数组：

int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };

先取一个增量 d = n/2 = 5，把每相隔 5 的数据分为一组，如下：

第一组 ---> 49 -- 13
第二组 ---> 38 -- 27
第三组 ---> 65 -- 49
第四组 ---> 97 -- 55
第五组 ---> 76 -- 04

每一组进行插入排序，如下：

第一组 ---> 13 -- 49
第二组 ---> 27 -- 38
第三组 ---> 49 -- 65
第四组 ---> 55 -- 97
第五组 ---> 04 -- 76

第一次的结果为：

{ 13, 27, 49, 55, 04, 49, 38, 65, 97, 76 };

取第二个增量 d2 = d/2 = 3，把每相隔 3 的数据分为一组，如下：

第一组 ---> 13 -- 55 -- 38 -- 76
第二组 ---> 27 -- 04 -- 65
第三组 ---> 49 -- 49 -- 97

每一组进行插入排序，如下：

第一组 ---> 13 -- 38 -- 55 -- 76
第二组 ---> 04 -- 27 -- 65
第三组 ---> 49 -- 49 -- 97

第二次的结果为：

{ 13, 04, 49, 38, 27, 49, 55, 65, 97, 76 };

取第三个增量 d3 = d2/2 = 1，把每相隔 1 的数据分为一组，这时开始直接插入排序即可，结果如下：
```
{ 04, 13, 27, 38, 49, 49, 55, 65, 76, 97 };
```

增量 d 取值为奇数。

3. 算法图解附视频

希尔排序图解

视频点此查看。

4. 算法代码

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        for (int d = arr.length / 2; d > 2; d /= 2) {
            for (int i = 0; i < d; i++) {
                insertSort(arr, i, d);
            }
        }
        insertSort(arr, 0, 1); 
    }

    // 插入排序
    public static void insertSort(int[] arr, int i, int d) {
        for (int a = i + d; a < arr.length; a += d) {    // a += d 
            for (int j = a; (j >= d) && (arr[j] < arr[j - d]); j -= d) {
                int temp = arr[j];
                arr[j] = arr[j - d];
                arr[j - d] = temp;
            }
        }
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以加QQ（2602138376）